package com.zjj.lbw.interview.funmath;

/**
 * @author zhanglei.zjj
 * @description 统计N 以内所以素数个数
 * @date 2023/8/31 17:41
 */
public class CountPrimes {
    public static int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }

        int count = 0;
        for (int i = 2; i < n; i++) {
            count += isPrime(i) ? 1 : 0;
        }

        return count;
    }

    private static boolean isPrime(int n) {
        // 这里其实遍历到根号x就可以了，因为比如 12，可以分解为 2 * 6，就没必要再比 根据 6 * 2来判断
        // 但是java中不太书写表示根号的，使用等式两边同时平方
        for (int i = 2; i * i <= n; i++) {
            // 在2 ~ (n - 1) 范围内如果能找到一个数可以整数，则说明为非素数
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static int eratosthenes(int n) {
        if (n <= 2) {
            return 0;
        }
        int count = 0;
        // 标记数组，false表示素数
        boolean[] flag = new boolean[n];
        for (int i = 2; i < n; i++) {
            if (!flag[i]) {
                count++;

                // 如果一个数是素数，那么 2 * j, 3 * j, 4 * j 一定是合数
                // 这些标志位倍增判断也会有重复的，比如 2 * 3 在i = 2时候判断了一次，3 * 2又在 i = 3时候判断了一次
                // 因此要3的时候要从 3 * 3 = 9开始
                for (int j = i * i; j < n; j+=i) {
                    flag[j] = true;
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
//        int i = eratosthenes(100);
        int i = countPrimes(100);
        System.out.println(i);
    }
}
